package main.scala

import main.scala.AST._
import scala.math.BigInt

object NativeFunctions {

  /**
   * Find Greatest Common Divisor (GCD) of two expressions.
   * @param g current value of GCD
   * @param e new term
   */
  def gcdHelper(g : List[Exp])(e : Exp) : List[Exp] = {
    g match {
      case Nil => e match {
        case Mul(l) => l
        case Add(List(t)) => List(t)
        case Add(t :: rest) => gcdHelper(List(evidence(t)))(Add(rest))
        case _ => List(e)
      }
      case t :: rest => (t, e) match {
        case (NumI(vt), NumI(v)) => {
          List(NumI(BigInt(vt.abs).gcd(BigInt(v.abs)).toInt))
        }
        case (_, NumI(v)) => gcdHelper(rest)(e)
        case (_, NumD(_)) => List(NumI(1))
        
        case (_, Var(_)) => if (g.contains(e)) List(e) else List(NumI(1))
//        case Neg(x)
        
//        case Pow
//        case Mod
        
        case (_, Add(l)) => l.foldLeft(g)(gcdHelper(_)(_))
        case (_, Mul(l)) => {
          gcdHelper(g)(Add(l.map(evidence).filterNot(NumI(1) == _)))
        }
        
        case _ => List(NumI(1))
      }
    }
  }
  
  
  /**
   * Find biggest term that can be put in evidence.
   * E.g. for Var(a) it returns Var(a) and not NumI(1).
   */
  def evidence(e : Exp) : Exp = {
    gcdHelper(Nil)(e) match {
      case Nil => NumI(1)
      case List(e) => e
      case l => Mul(l)
    }
  }
  
}
